#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2e5+5,A=1e6+5;
template<typename T>inline void read(T &x){
    int f=1; x=0; char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-f;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
template<typename T>void write(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int n;
int a[MAX];
namespace solve1{
    const int N=2005;
    ll f[N][N],g[N],ff[N],fg[N][N];
    void main(){
        memset(f,0xcf,sizeof(f));
        memset(ff,0xcf,sizeof(ff));
        memset(fg,0xcf,sizeof(fg));
        f[0][0]=ff[0]=fg[0][0]=0;
        ll ans=0;
        vector<int> b;
        for(int i=1;i<=n;i++) b.push_back(a[i]);
        sort(b.begin(),b.end());
        b.erase(unique(b.begin(),b.end()),b.end());
        for(int i=1;i<=n;i++) a[i]=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
        for(int i=1;i<=n;i++){
            if(a[i]==a[i-1]) g[i]=g[i-1]+b[a[i]-1];
            else g[i]=g[i-1];
        }
        g[n+1]=g[n];
        for(int i=1;i<=n;i++){
            for(int j=0;j<i-1;j++){
                ll t=g[i-1]-g[j+1]+(a[j]==a[i]?b[a[i]-1]:0);
                f[i][i-1]=max(f[i][i-1],ff[j]+t);
                f[i][i-1]=max(f[i][i-1],fg[j][a[j+1]]+t+b[a[j+1]-1]);
            }
            for(int j=0;j<i-1;j++){
                f[i][j]=max(f[i][j],f[i-1][j]+(a[i-1]==a[i]?b[a[i]-1]:0));
            }
            for(int j=0;j<i;j++){
                ff[i]=max(ff[i],f[i][j]);
                fg[i][a[j]]=max(fg[i][a[j]],f[i][j]);
                ans=max(ans,f[i][j]+g[n]-g[i+1]+(a[i+1]==a[j]?b[a[j]-1]:0));
            }
        }
        #ifdef DEBUG
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(f[i][j]<0) cout<<"-1 ";
                else cout<<f[i][j]<<' ';
            }
            cout<<'\n';
        }
        #endif
        write(ans); putchar('\n');
    }
}
void solve(){
    read(n); 
    for(int i=1;i<=n;i++) read(a[i]);
    if(n<=2000){solve1::main();return ;}
    write(-1); putchar('\n');
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T; read(T);
    while(T--) solve();
    return 0;
}
/*
:-(
*/